package _dp_base;

import java.util.Arrays;

/**
 * 70. 爬楼梯
 */
public class No70 {
    private int[] cache;

    /**
     * 1. 递归
     */
    public int climbStairs(int n) {
        cache = new int[n + 1];
        Arrays.fill(cache, -1);
        return dfs(n);
    }

    private int dfs(int i) {
        if (i < 0) return 0;
        else if (cache[i] != -1) return cache[i];
        else if (i == 0) return cache[i] = 1;
        else return cache[i] = dfs(i - 1) + dfs(i - 2);
    }

    /**
     * 2. 迭代
     */
    public int climbStairs2(int n) {
        int[] f = new int[n + 3];
        f[0] = 1;
        for (int i = 0; i <= n; i++) {
            f[i + 2] = f[i + 1] + f[i];
        }
        return f[n + 2];
    }

    /**
     * 3. 空间优化
     */
    public int climbStairs3(int n) {
        int f0 = 1, f1 = 0;
        for (int i = 0; i <= n; i++) {
            int temp = f1;
            f1 = f1 + f0;
            f0 = temp;
        }
        return f1;
    }
}
